import java.util.*;

/**
 * @author SongJun
 * @description 752打开转盘锁(BFS)
 * @date 2021/9/10 13:45
 */
public class Openthelock {
    public static void main(String[] args) {
        Openthelock instance = new Openthelock();
        String[] deadends = {"8887","8889","8878","8898","8788","8988","7888","9888"};
        String target = "8866";
        System.out.println(instance.openLock(deadends, target));
    }

    //BFS
    public int openLock(String[] deadends, String target) {
        int step = 0;
        String start = "0000";
        Set<String> memory = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                String item = queue.poll();
                if(item.equals(target)){
                    return step;
                }
                if(memory.contains(item)){
                    continue;
                }
                memory.add(item);
                if(!isValid(deadends,item)){
                    continue;
                }
                for(int j=0; j<8; j++){
                    queue.offer(move(item,j));
                }
            }
            step++;
        }
        return -1;
    }

    //拨动一次锁
    String move(String target, int type){
        char[] cs = target.toCharArray();
        int index = type / 2;//操作位置
        int module = type % 2;//操作方式: 0加一; 1减一
        if(cs[index] == '9' && module == 0){
            cs[index] = '0';
        } else if(cs[index] == '0' && module == 1){
            cs[index] = '9';
        } else {
            if(module == 0){
                cs[index] += 1;
            } else {
                cs[index] -= 1;
            }
        }
        return new String(cs);
    }

    boolean isValid(String[] deadends, String target){
        for(String deadend : deadends){
            if(deadend.equals(target)){
                return false;
            }
        }
        return true;
    }
}
